package leetcode.editor.cn;

public class P399EvaluateDivisionNote {
    public static void main(String[] args) {
        UF uf = new UF(5);
        uf.union(0, 1);
        uf.union(1, 4);
        System.out.println(uf.isConnected(0, 4));

    }
    static class UF{
        private Integer[] parent;
        private Integer[] size;

        public UF(Integer len) {
            parent = new Integer[len];
            size = new Integer[len];
            for (int i = 0; i < len; i++) {
                parent[i] = i;
                size[i] = 1;
            }
        }

        public Boolean isConnected(int v, int w) {
            Integer rootP = findParent(v);
            Integer rooQ = findParent(w);
            return rooQ == rootP;
        }

        public Integer findParent(int v) {
            Integer father = this.parent[v];
            while (this.parent[father] != father) {
                this.parent[father] = this.parent[this.parent[father]];
                father = this.parent[father];
            }
            return father;
        }

        public void  union(int v, int w) {
            Integer rootP = findParent(v);
            Integer rootQ = findParent(w);
            if (size[rootP] > size[rootQ]) {
                parent[rootQ] = rootP;
                size[rootP] += size[rootQ];
            }else{
                parent[rootP] = rootQ;
                size[rootQ] += size[rootP];
            }
        }
    }
}
